{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Boxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeBoxes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除盒子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一些不同颜色的盒子<meta charset=\"UTF-8\" />&nbsp;<code>boxes</code>&nbsp;，盒子的颜色由不同的正数表示。</p>\n",
    "\n",
    "<p>你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 <code>k</code> 个盒子（<code>k&nbsp;&gt;= 1</code>），这样一轮之后你将得到 <code>k * k</code> 个积分。</p>\n",
    "\n",
    "<p>返回 <em>你能获得的最大积分和</em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [1,3,2,2,2,3,4,3,1]\n",
    "<strong>输出：</strong>23\n",
    "<strong>解释：</strong>\n",
    "[1, 3, 2, 2, 2, 3, 4, 3, 1] \n",
    "----&gt; [1, 3, 3, 4, 3, 1] (3*3=9 分) \n",
    "----&gt; [1, 3, 3, 3, 1] (1*1=1 分) \n",
    "----&gt; [1, 1] (3*3=9 分) \n",
    "----&gt; [] (2*2=4 分)\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [1,1,1]\n",
    "<strong>输出：</strong>9\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxes = [1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= boxes.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= boxes[i]&nbsp;&lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-boxes](https://leetcode.cn/problems/remove-boxes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-boxes](https://leetcode.cn/problems/remove-boxes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,2,2,3,4,3,1]', '[1,1,1]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        \n",
    "        boxes = [(a, len(list(b))) for a, b in groupby(boxes)]\n",
    "        n = len(boxes)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(i, j, k):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            # cnt = 0\n",
    "            # while i + cnt <= j and boxes[i + cnt] == boxes[i]:\n",
    "            #     cnt += 1\n",
    "            # i2 = i + cnt\n",
    "            # remove all boxes before i2 (k = 0)\n",
    "            ans = dp(i+1, j, 0) + (k + boxes[i][1]) ** 2\n",
    "            for x in range(i+1, j+1):\n",
    "                if boxes[x][0] == boxes[i][0]:\n",
    "                    # or keep all boxes before i2 until same color appear again (\"x\")\n",
    "                    # boxes between i2 and x - 1 are different color (k = 0)\n",
    "                    # box \"x\" could inherit count from previous (k + cnt)\n",
    "                    ans = max(ans, dp(i+1, x-1, 0) + dp(x, j, k+boxes[i][1]))\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, n-1, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            tmp = i\n",
    "            while tmp + 1 < n and boxes[tmp] == boxes[tmp + 1]:\n",
    "                tmp += 1\n",
    "            cnt = k + tmp - i + 1\n",
    "            ans = cnt * cnt + dfs(tmp + 1, j, 0)\n",
    "            for m in range(tmp + 2, j + 1):\n",
    "                if boxes[i] == boxes[m] and boxes[m - 1] != boxes[m]:\n",
    "                    ans = max(ans, dfs(tmp + 1, m - 1, 0) + dfs(m, j, cnt))\n",
    "            return ans\n",
    "        return dfs(0, n - 1, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        memo = {}\n",
    "        # 已知boxes[l]有n个的情况下，boxes[l:r]能获得的最大积分\n",
    "        def dp(l, r, n):\n",
    "            nonlocal memo, boxes\n",
    "            if memo.get((l, r, n)):\n",
    "                return memo[(l, r, n)]\n",
    "            \n",
    "            # 只剩最后一个数字，直接结算\n",
    "            if l == r - 1:\n",
    "                return (n + 1) * (n + 1)\n",
    "            \n",
    "            # 发现邻居和自己相同，和他加一起结算\n",
    "            if boxes[l] == boxes[l + 1]:\n",
    "                return dp(l + 1, r, n + 1)\n",
    "            \n",
    "            # 先直接结算，之后再看有没有和自己一样的\n",
    "            res = (n + 1) * (n + 1) + dp(l + 1, r, 0)\n",
    "\n",
    "            # 已知下一个和自己不一样，从下下个开始找和自己一样的兄弟\n",
    "            for l2 in range(l + 2, r):\n",
    "                # 找到兄弟了\n",
    "                if boxes[l2] == boxes[l]:\n",
    "                    res = max(\n",
    "                        res,\n",
    "                        # 让自己的下一个到这个兄弟之前结算,\n",
    "                        # 然后让自己和兄弟加起来结算，\n",
    "                        # 然后取最大值\n",
    "                        dp(l + 1, l2, 0) + dp(l2, r, n + 1)\n",
    "                    )\n",
    "            memo[(l, r, n)] = res\n",
    "            return res\n",
    "        # 初始状态为 已知boxes[0]有0个的情况下， boxes[0:]能获得的最大积分\n",
    "        return dp(0, len(boxes), 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        g = [[a,len(list(b))] for a,b in groupby(boxes)]\n",
    "        nums,cnt = zip(*g)\n",
    "        @cache\n",
    "        def f(i,j,c):\n",
    "            if i == j : return 0 \n",
    "            c += cnt[i] \n",
    "            return max(\n",
    "                [f(i+1,j,0)+c*c] + \n",
    "                [f(i+1,k,0)+f(k,j,c) for k in range(i+1,j) if nums[i] == nums[k]]\n",
    "            ) \n",
    "        return f(0,len(nums),0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        g = [[a,len(list(b))] for a,b in groupby(boxes)]\n",
    "        nums,cnt = zip(*g)\n",
    "        @cache\n",
    "        def f(i,j,c):\n",
    "            if i == j : return 0 \n",
    "            c += cnt[i] \n",
    "            return max(\n",
    "                [f(i+1,j,0)+c*c] + \n",
    "                [f(i+1,k,0)+f(k,j,c) for k in range(i+1,j) if nums[i] == nums[k]]\n",
    "            ) \n",
    "        return f(0,len(nums),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        memo={}\n",
    "        def dfs(l,r,n):\n",
    "            if (l,r,n) in memo:\n",
    "                return memo[(l,r,n)]\n",
    "            if l+1==r:\n",
    "                return (n+1)*(n+1)\n",
    "            if boxes[l]==boxes[l+1]:\n",
    "                return dfs(l+1,r,n+1)\n",
    "            res=(n+1)*(n+1)+dfs(l+1,r,0) \n",
    "\n",
    "            for l2 in range(l+2,r):\n",
    "                if boxes[l2]==boxes[l]:\n",
    "                    res=max(res,dfs(l+1,l2,0)+dfs(l2,r,n+1))\n",
    "\n",
    "            memo[(l,r,n)]=res\n",
    "            return res \n",
    "\n",
    "        return dfs(0,len(boxes),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        # 预先统计相同次数，对数据进行处理\n",
    "        # g = [[a,len(list(b))] for a,b in groupby(boxes)]\n",
    "        # nums,cnt = zip(*g)\n",
    "\n",
    "        #第二种方法统计\n",
    "        nums = list()\n",
    "        cnt = list()\n",
    "        c = 0\n",
    "        x = boxes[0]\n",
    "        for i in range(len(boxes)):\n",
    "            if x == boxes[i]:\n",
    "                c += 1\n",
    "            else:\n",
    "                nums.append(x)\n",
    "                cnt.append(c) \n",
    "                c = 1\n",
    "                x = boxes[i]\n",
    "        nums.append(x)\n",
    "        cnt.append(c)\n",
    "        # print(nums,cnt)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j,c):  #起始下标i(以0开始)，结束下标j，c表示在下标i左面紧接着有c个元素值和nums[i]相同\n",
    "            if i == j: # 结束\n",
    "                return 0 \n",
    "            c += cnt[i] #加上nums[i] 对应的次数\n",
    "            res = dfs(i+1,j,0)+c*c \n",
    "            for k in range(i+1,j):\n",
    "                if nums[i] == nums[k]:\n",
    "                    res = max(res,dfs(i+1, k, 0)+dfs(k, j, c)) #dfs(k, j, c)会继续往下统计\n",
    "            return res\n",
    "            \n",
    "        return dfs(0, len(nums), 0)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.memo= [[[0] * 100 for _ in range(100)] for _ in range(100)]\n",
    "\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        return self.dp(boxes,0,len(boxes)-1,0)\n",
    "        \n",
    "    def dp(self,boxes:List[int],l:int,r:int,k:int)->int:\n",
    "        if l>r:\n",
    "            return 0\n",
    "        if self.memo[l][r][k]!=0:\n",
    "            return self.memo[l][r][k]\n",
    "        r1,k1=r,k\n",
    "        while r1>l and boxes[r1]==boxes[r1-1]:\n",
    "            r1-=1\n",
    "            k1+=1\n",
    "        if r1!=r:\n",
    "            self.memo[l][r][k]=self.dp(boxes,l,r1,k1)\n",
    "            return self.memo[l][r][k]\n",
    "        else:\n",
    "            self.memo[l][r][k]=self.dp(boxes,l,r-1,0)+(k+1)*(k+1)\n",
    "            for i in range(l,r):\n",
    "                if boxes[i]==boxes[r]:\n",
    "                    self.memo[l][r][k]=max(self.memo[l][r][k],self.dp(boxes,i+1,r-1,0)+self.dp(boxes,l,i,k+1))\n",
    "            return self.memo[l][r][k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        remains = [0 for _ in range(len(boxes))]\n",
    "        note = {}\n",
    "        maxn = 0\n",
    "        for i in range(len(boxes) - 1, -1, -1):\n",
    "            if boxes[i] not in note:\n",
    "                remains[i] = 0\n",
    "                note[boxes[i]] = 1\n",
    "            else:\n",
    "                remains[i] = note[boxes[i]]\n",
    "                note[boxes[i]] += 1\n",
    "                maxn = max(note[boxes[i]], maxn)\n",
    "        dp = [[[0 for _ in range(maxn + 1)] for _ in range(len(boxes))] for _ in range(len(boxes))]\n",
    "        for l in range(1, len(boxes) + 1):\n",
    "            for i in range(len(boxes)):\n",
    "                j = i + l - 1\n",
    "                if j >= len(boxes):\n",
    "                    break\n",
    "                r = j\n",
    "                while r - 1 >= 0 and boxes[r - 1] == boxes[j]:\n",
    "                    r -= 1\n",
    "                for k in range(remains[j] + 1):\n",
    "                    if i == j:\n",
    "                        dp[i][j][k] = (k + 1) * (k + 1)\n",
    "                    elif r != j:\n",
    "                        dp[i][j][k] = dp[i][j - 1][k + 1]\n",
    "                    else:\n",
    "                        for p in range(i, r):\n",
    "                            if p == r - 1:\n",
    "                                dp[i][j][k] = max(dp[i][j][k], dp[i][r - 1][0] + (k + 1) * (k + 1))\n",
    "                            elif boxes[p] == boxes[j]:\n",
    "                                dp[i][j][k] = max(dp[i][j][k], dp[i][p][k + 1] + dp[p + 1][r - 1][0])\n",
    "        return dp[0][len(boxes) - 1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        dp = [[[0 for k in range(n+1)] for j in range(n)] for i in range(n)]\n",
    "        return self.process4(boxes, 0, n-1, 0, dp)\n",
    "\n",
    "    # arr[L...R]消除，而且前面跟着K个arr[L]这个数\n",
    "    # 返回：所有东西都消掉，最大得分\n",
    "    def process4(self, arr, L, R, K, dp):\n",
    "        if L > R:\n",
    "            # dp[L][R][K] = 0  # 已经是0了不需要赋值了\n",
    "            return 0\n",
    "        if dp[L][R][K] >0:\n",
    "            return dp[L][R][K]\n",
    "        if L == R:\n",
    "            dp[L][R][K] = (K+1) * (K+1)\n",
    "            return (K+1) * (K+1)\n",
    "        last = L\n",
    "        while last + 1 <= R and arr[last+1] == arr[L]:\n",
    "            last += 1\n",
    "        pre = K + last - L\n",
    "        ans = self.process4(arr, last+1, R, 0, dp) + (pre+1) * (pre+1)\n",
    "        for i in range(last+1, R+1):\n",
    "            if arr[i] == arr[last] and arr[i-1] != arr[last]:  # 1 1 1 1 2 只调用第一个就可以了，后面会自动合并\n",
    "                ans = max(ans, self.process4(arr, last+1, i-1, 0, dp) + self.process4(arr, i, R, pre+1, dp))  # 前面K+1个数和第i个数一起消掉，这里是pre+1\n",
    "        dp[L][R][K] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes1(self, boxes: List[int]) -> int:\n",
    "        N = len(boxes)\n",
    "        return self.func1(boxes, 0, N - 1, 0)\n",
    "    # arr[L...R]消除，而且前面跟着K个arr[L]这个数\n",
    "\t# 返回：所有东西都消掉，最大得分\n",
    "    def func1(self, arr, L, R, K):\n",
    "        # base case\n",
    "        # 当区间不成立的时候，结果为0\n",
    "        if L > R:\n",
    "            return 0\n",
    "        # 所有可能性的示例，见注释3\n",
    "        \n",
    "        # 可能性1：K个arr[L]和arr[L]一起消掉    # 详见，注释1\n",
    "        #                                    前 K + 1的得分\n",
    "        #     后面，其他的得分\n",
    "        ans = self.func1(arr, L + 1, R, 0) + (K + 1) * (K + 1)\n",
    "\n",
    "        # 前面的K个X，和arr[L]数，合在一起了，现在有K+1个arr[L]位置的数\n",
    "        # 详见，注释2\n",
    "        for i in range(L + 1, R + 1, 1):\n",
    "            # 如果有任何一个位置的i，和L相同，则尝试，将他们看做1组连续的\n",
    "            #   获得所有可能连续性下的结果，返回最大的结果\n",
    "            # 由于，arr[L]肯定和前面的K个X相同,所以，将他们做为一个统一的外部整体\n",
    "            if arr[i] == arr[L]:\n",
    "                #              i的左侧部分[L + 1, i - 1]\n",
    "                #                                            i的右侧部分，[i, R],包括前面的K + 1个arr[i]\n",
    "                #                                                             注意，这里还要+1，因为包含arr[L]这个值\n",
    "                ans = max(ans, self.func1(arr, L + 1, i - 1, 0) + self.func1(arr, i, R, K + 1))\n",
    "\n",
    "        return ans\n",
    "    \n",
    "    # 上面的优化版本，同时加入了傻缓存\n",
    "    def removeBoxes(self, boxes):\n",
    "        N = len(boxes)\n",
    "        # 傻缓存L、R、K3个变量\n",
    "        dp = [[[0 for k in range(N)] for j in range(N)] for i in range(N)]\n",
    "        ans = self.process2(boxes, 0, N - 1, 0, dp)\n",
    "        return ans\n",
    "    \n",
    "    # 递归逻辑\n",
    "    def process2(self, boxes, L, R, K, dp):\n",
    "        if L > R:\n",
    "            return 0\n",
    "\n",
    "        # 傻缓存的返回\n",
    "        if dp[L][R][K] > 0:\n",
    "            return dp[L][R][K]\n",
    "\n",
    "        # 找到和前K个，前缀中最后一个相同的位置\n",
    "        # 示例：\n",
    "        # 1,1,1,1,1,5\n",
    "\t\t# 3 4 5 6 7 8\n",
    "\t\t#         !\n",
    "        # [L, last)\n",
    "        last = L\n",
    "        while last + 1 <= R and boxes[last + 1] == boxes[L]:\n",
    "            last += 1\n",
    "            \n",
    "        # 前K个值，变为：K + [L, last)之间这么多相同的\n",
    "        #   因为，相同的连续的一组，肯定是最优的\n",
    "        pre = K + last - L\n",
    "        # 现在的pre，就相当于func1中的K。\n",
    "        # 其他尝试方式和func1相同\n",
    "        # 情况1，pre和last位置合并，[last + 1, R]合并\n",
    "        #                                                               注意，这里的k，肯定是0\n",
    "        ans = (pre + 1) * (pre + 1) + self.process2(boxes, last + 1, R, 0, dp)\n",
    "        # 其他情况，pre + 1,和其他相同位置的合并\n",
    "        #              因为last + 1，肯定是不会自己boxes[L]相同，所以，从last + 2开始比较\n",
    "        for i in range(last + 2, R + 1, 1):\n",
    "            # 确保找到和boxe[L]相同区域的，第一的位置\n",
    "            #                           值相同，且，前一个的值，和自己不同，说明自己是第一个的位置\n",
    "            #  详见，注释4\n",
    "            if boxes[i] == boxes[L] and boxes[i - 1] != boxes[L]:\n",
    "                #                                                                                        注意，前面是pre + 1个。因为还有last这个\n",
    "                #              [last + 1, i - 1]部分\n",
    "                #                                                             pre + 1 和 [i, R]部分\n",
    "                ans = max(ans, self.process2(boxes, last + 1, i - 1, 0, dp) + self.process2(boxes, i, R, pre + 1, dp))\n",
    "           \n",
    "        # 缓存一下     \n",
    "        dp[L][R][K] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(n)]\n",
    "        for l in range(n-1,-1,-1):\n",
    "            for r in range(l,n):\n",
    "                for k in range(n-r):\n",
    "                    if r > l and boxes[r] == boxes[r-1]:\n",
    "                        dp[l][r][k] = dp[l][r-1][k+1]\n",
    "                        continue\n",
    "                    # 状态初始化：状态 dp[l][r][k] 不代表 boxes[r] 后面真的有 k 个颜色相\n",
    "                    # 同的盒子，而是假设存在这么一种状态，并且把这种状态的最大值保留下来\n",
    "                    dp[l][r][k] = dp[l][r-1][0] + (k+1)**2\n",
    "                    for i in range(l, r):\n",
    "                        if boxes[i] == boxes[r]:\n",
    "                            dp[l][r][k] = max(dp[l][r][k], dp[l][i][k+1] + dp[i+1][r-1][0])\n",
    "        return dp[0][n-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\r\n",
    "        n = len(boxes)\r\n",
    "        f = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]\r\n",
    "        for l in range(n):\r\n",
    "            for i in range(n-l):\r\n",
    "                j = i+l\r\n",
    "                for t in range(n-j):\r\n",
    "                    if j-1 >= i and boxes[j-1] == boxes[j]:\r\n",
    "                        f[i][j][t] = f[i][j-1][t+1]\r\n",
    "                        continue\r\n",
    "                    f[i][j][t] = max(f[i][j][t], f[i][j-1][0]+pow(t+1, 2))\r\n",
    "                    for k in range(i, j):\r\n",
    "                        if boxes[k] == boxes[j]:\r\n",
    "                            f[i][j][t] = max(\r\n",
    "                                f[i][j][t], f[i][k][t+1]+f[k+1][j-1][0])\r\n",
    "        return f[0][n-1][0]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        dp = [[[0] * (n + 1) for _ in range(n+1)] for _ in range(n+1)]\n",
    "\n",
    "        for l in range(n):\n",
    "            # 区间长度\n",
    "            for i in range(n - l):\n",
    "                j = i + l\n",
    "                for t in range(n-j):\n",
    "                    # 尾部额外多出来t个与ar 相同的数\n",
    "                    dp[i][j][t] = max(dp[i][j][t], dp[i][j-1][0] + pow(t+1,2))\n",
    "                    for k in range(i, j):\n",
    "                        # k就是分治思路的分割点 ，需要遍历\n",
    "\n",
    "                        if boxes[k] == boxes[j]:\n",
    "                            dp[i][j][t] = max(dp[i][j][t], dp[i][k][t+1] + dp[k+1][j-1][0])\n",
    "        return dp[0][n-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "\n",
    "        dp = [[[0] * (n + 1) for _ in range(n+1)] for _ in range(n+1)]\n",
    "\n",
    "        for l in range(n):\n",
    "            for i in range(n-l):\n",
    "                j = i + l\n",
    "                ##########\n",
    "                for t in range(n-j):\n",
    "                    dp[i][j][t] = max(dp[i][j][t],dp[i][j-1][0] + pow(t+1, 2))\n",
    "                    for k in range(i, j):\n",
    "                        if boxes[k] == boxes[j]:\n",
    "                            dp[i][j][t] = max(dp[i][j][t], dp[i][k][t+1] + dp[k+1][j-1][0])\n",
    "        return dp[0][n-1][0]\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 依赖于 全部的长度1 及 尾部状态\n",
    "class Solution:\n",
    "    def removeBoxes(self, bs: List[int]) -> int:\n",
    "        N = len(bs)\n",
    "        dp = [[[0]* (N+1) for _ in range(N+1)] for _ in range(N+1)]\n",
    "        for l in range(N):   # l++ 从小段 到 大段\n",
    "            for i in range(N-l): # i++ 起点 从小到大\n",
    "                j = i + l ;\n",
    "                for t in range(N-j): # 尾部tail 同数 从小 到 大\n",
    "                    dp[i][j][t]=max(dp[i][j][t],dp[i][j-1][0]+pow(t+1,2))\n",
    "                    for k in range(i,j) : # 枚举 分割点 k\n",
    "                        if bs[k] == bs[j]:\n",
    "                            dp[i][j][t]=max(dp[i][j][t],\\\n",
    "                                dp[i][k][t+1]+dp[k+1][j-1][0])\n",
    "        return dp[0][N - 1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\r\n",
    "        n = len(boxes)\r\n",
    "        f = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]\r\n",
    "        for l in range(n):\r\n",
    "            for i in range(n-l):\r\n",
    "                j = i+l\r\n",
    "                for t in range(n-j):\r\n",
    "                    f[i][j][t] = max(f[i][j][t], f[i][j-1][0]+pow(t+1, 2))\r\n",
    "                    for k in range(i, j):\r\n",
    "                        if boxes[k] == boxes[j]:\r\n",
    "                            f[i][j][t] = max(\r\n",
    "                                f[i][j][t], f[i][k][t+1]+f[k+1][j-1][0])\r\n",
    "        return f[0][n-1][0]\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, bs: List[int]) -> int:\n",
    "        N = len(bs)\n",
    "        dp = [[[0]* (N+1) for _ in range(N+1)] for _ in range(N+1)]\n",
    "        for l in range(N): # 长度从小到大\n",
    "            for i in range(N-l): # 以 i 为 开头\n",
    "                j = i + l           # 以 j 为 终点\n",
    "                for t in range(N-j): \n",
    "                    dp[i][j][t] = max(dp[i][j][t], dp[i][j-1][0]+pow(t+1,2)) \n",
    "                    for k in range(i,j) : # 枚举 分割点 k\n",
    "                        if bs[k] == bs[j]:\n",
    "                            dp[i][j][t]=max(dp[i][j][t], dp[i][k][t+1]+dp[k+1][j-1][0])\n",
    "        return dp[0][N-1][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        f = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                for k in range(n-j-1, -1, -1):\n",
    "                    f[i][j][k] = max(f[i][j][k], f[i][j-1][0] + (k+1)**2)\n",
    "                    for t in range(i, j):\n",
    "                        if boxes[t] == boxes[j]:\n",
    "                            f[i][j][k] = max(f[i][j][k], f[t+1][j-1][0] + f[i][t][k+1])\n",
    "        return f[0][n-1][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        ma=max(Counter(boxes).values())\n",
    "        count = []\n",
    "        boxes_ = [boxes[0]]\n",
    "        cnt = 1\n",
    "        for i in range(1, len(boxes)):\n",
    "            if boxes[i] == boxes[i - 1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                count.append(cnt)\n",
    "                boxes_.append(boxes[i])\n",
    "                cnt = 1\n",
    "        count.append(cnt)\n",
    "        boxes = boxes_\n",
    "        dp = [[[0] * (ma + 1) for _ in range(len(boxes))] for _ in range(len(boxes))]\n",
    "\n",
    "        def calc(l, r, k):\n",
    "            if l > r: return 0\n",
    "            if dp[l][r][k]: return dp[l][r][k]\n",
    "            dp[l][r][k] = max(dp[l][r][k], calc(l, r - 1, 0) + (k + count[r]) ** 2)\n",
    "            for p in range(r - 1, l - 1, -1):\n",
    "                if boxes[p] == boxes[r]:\n",
    "                    dp[l][r][k] = max(dp[l][r][k], calc(l, p, k+count[r]) + calc(p + 1, r - 1, 0))\n",
    "            return dp[l][r][k]\n",
    "\n",
    "        return calc(0, len(boxes) - 1, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(l, r, k):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            while l < r and boxes[r] == boxes[r-1]:\n",
    "                r -= 1\n",
    "                k += 1\n",
    "            ans = dp(l, r - 1, 0) + (k + 1) ** 2\n",
    "            for i in range(l, r):\n",
    "                if boxes[i] == boxes[r]:\n",
    "                    ans = max(ans, dp(l, i, k + 1) + dp(i + 1, r - 1, 0))\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, len(boxes) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @cache\n",
    "        def recur(l,r,k):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if l == r:\n",
    "                return (k+1)*(k+1)\n",
    "            while l < r:\n",
    "                if boxes[r] != boxes[r-1]:\n",
    "                    break\n",
    "                k += 1\n",
    "                r -= 1\n",
    "            res = recur(l,r-1,0) + (k+1)**2\n",
    "            for i in range(l,r):\n",
    "                if boxes[i] == boxes[r]:\n",
    "                    res = max(res,recur(l,i,k+1) + recur(i+1,r-1,0))\n",
    "            return res\n",
    "        return recur(0,len(boxes)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from collections import *\n",
    "from itertools import *\n",
    "from queue import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def f(l, r, k):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            while r > l and boxes[r] == boxes[r-1]:\n",
    "                r -= 1\n",
    "                k += 1\n",
    "            res = f(l, r-1, 0) + (k + 1) ** 2\n",
    "            for i in range(l,r):\n",
    "                if boxes[i] == boxes[r]:\n",
    "                    res = max(res, f(l, i, k+1) + f(i+1, r-1, 0))\n",
    "            return res\n",
    "        return f(0, len(boxes) - 1, 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "s = Solution()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#移除盒子，输入：boxes = [1,3,2,2,2,3,4,3,1]输出：23\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r,k):\n",
    "            if l>r:return 0\n",
    "            while r>l and boxes[r]==boxes[r-1]:#颜色相同\n",
    "                r-=1\n",
    "                k+=1#相同颜色的数目\n",
    "            res=dfs(l,r-1,0)+(k+1)**2#去除所有颜色相同的，重新开始\n",
    "            for i in range(l,r):\n",
    "                if boxes[i]==boxes[r]:\n",
    "                    res=max(res,dfs(l,i,k+1)+dfs(i+1,r-1,0))#右边为什么是0呢；\n",
    "            return res \n",
    "        return dfs(0,len(boxes)-1,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(l,r,k):\n",
    "            if l>r:return 0\n",
    "            while r>l and boxes[r]==boxes[r-1]:#颜色相同\n",
    "                r-=1\n",
    "                k+=1#相同颜色的数目\n",
    "            res=dfs(l,r-1,0)+(k+1)**2#去除所有颜色相同的，重新开始\n",
    "            for i in range(l,r):\n",
    "                if boxes[i]==boxes[r]:\n",
    "                    res=max(res,dfs(l,i,k+1)+dfs(i+1,r-1,0))#右边为什么是0呢；\n",
    "            return res \n",
    "        return dfs(0,len(boxes)-1,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i >= j:\n",
    "                return k * k\n",
    "            \n",
    "            k += 1\n",
    "            while i + 1 < j and boxes[i] == boxes[i + 1]:\n",
    "                i += 1\n",
    "                k += 1\n",
    "            mx = k * k + dfs(i + 1, j, 0)\n",
    "\n",
    "            for m in range(i + 1, j):\n",
    "                if boxes[i] == boxes[m]:\n",
    "                    mx = max(mx, dfs(i + 1, m, 0) + dfs(m, j, k))\n",
    "            return mx\n",
    "\n",
    "\n",
    "        return dfs(0, len(boxes), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r, k):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            while l < r and boxes[r] == boxes[r - 1]:\n",
    "                r -= 1 \n",
    "                k += 1 \n",
    "            best = dfs(l, r - 1, 0) + (k + 1) ** 2\n",
    "            for i in range(l, r):\n",
    "                if boxes[i] == boxes[r]:\n",
    "                    best = max(best, dfs(l, i, k + 1) + dfs(i + 1, r - 1, 0))\n",
    "            return best\n",
    "        return dfs(0, n - 1, 0)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        seen = {}\n",
    "        def func(c, i, j):    # 返回左侧尚有 c 个 boxes[i] 的情况下，boxes[i:j+1] 的最大结果\n",
    "            if i == j:\n",
    "                return (c+1)*(c+1)\n",
    "            if (c, i, j) not in seen:\n",
    "                if boxes[i] == boxes[i+1]:\n",
    "                    res = func(c+1, i+1, j)\n",
    "                else:\n",
    "                    res = (c+1)*(c+1) + func(0, i+1, j)\n",
    "                    for k in range(i+1, j+1):\n",
    "                        if boxes[i] == boxes[k]:\n",
    "                            cur = func(c+1, k, j) + func(0, i+1, k-1)\n",
    "                            res = max(res, cur)\n",
    "                seen[c, i, j] = res\n",
    "            return seen[c, i, j]\n",
    "        \n",
    "        n = len(boxes)\n",
    "        return func(0, 0, n-1)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def f(l: int, r: int, n: int) -> int: # 已知box[l]有n个box[l:r]最大积分\n",
    "            if l == r - 1:\n",
    "                return (n + 1) * (n + 1)\n",
    "            if boxes[l] == boxes[l + 1]:\n",
    "                return f(l + 1, r, n + 1)\n",
    "            res = (n + 1) * (n + 1) + f(l + 1, r, 0)\n",
    "            for l2 in range(l+2, r):\n",
    "                if boxes[l2] == boxes[l]:\n",
    "                    res = max(res, f(l + 1, l2, 0) + f(l2, r, n + 1))\n",
    "            return res\n",
    "        \n",
    "        return f(0, len(boxes), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(l, r, n):\n",
    "            if l == r:\n",
    "                return (n + 1) ** 2\n",
    "            if boxes[l] == boxes[l+1]:\n",
    "                return dfs(l+1, r, n+1)\n",
    "            res = (n+1) ** 2 + dfs(l+1, r, 0)\n",
    "            for l1 in range(l+2, r+1):\n",
    "                if boxes[l1] == boxes[l]:\n",
    "                    res = max(res, dfs(l+1, l1-1, 0) + dfs(l1, r, n+1))\n",
    "            return res\n",
    "        return dfs(0, len(boxes)-1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(l, r, n):\n",
    "            if l == r:\n",
    "                return (n+1) ** 2\n",
    "            if boxes[l] == boxes[l+1]:\n",
    "                return dfs(l+1, r, n+1)\n",
    "            res = (n+1) **2 + dfs(l+1, r, 0)\n",
    "            for l2 in range(l+2, r+1):\n",
    "                if boxes[l2] == boxes[l]:\n",
    "                    res = max(res, dfs(l+1, l2-1, 0) + dfs(l2, r, n+1))\n",
    "            return res\n",
    "        return dfs(0, len(boxes)-1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "\n",
    "        @cache\n",
    "        def f(l, r, k):\n",
    "            if l > r: return 0\n",
    "            ans = f(l + 1, r, 0) + (k + 1) ** 2\n",
    "\n",
    "            for i in range(l + 1, r + 1):\n",
    "                if boxes[i] != boxes[l]:\n",
    "                    continue\n",
    "                \"\"\"\n",
    "                xxxxx  x  yzt x\n",
    "                k个[l] l      i\n",
    "                \"\"\"\n",
    "                p = f(l + 1, i - 1, 0) + f(i, r, k + 1)\n",
    "                ans = max(ans, p)\n",
    "            return ans\n",
    "        \n",
    "        return f(0, n - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        n = len(boxes)\n",
    "        dp = [[[-1]*n for _ in range(n)] for _ in range(n)]\n",
    "        def f(l, r, k):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if dp[l][r][k] != -1:\n",
    "                return dp[l][r][k]\n",
    "            s = l\n",
    "            while s+1 <= r and boxes[s+1] == boxes[l]:\n",
    "                s += 1\n",
    "            ret = s - l + 1 + k\n",
    "            ans = ret*ret + f(s+1, r, 0)\n",
    "            for i in range(s+2, r+1):\n",
    "                if boxes[i] == boxes[l] and boxes[i] != boxes[i-1]:\n",
    "                    ans = max(ans, f(i, r, ret) + f(s+1, i-1, 0))\n",
    "            dp[l][r][k] = ans\n",
    "            return ans\n",
    "        return f(0, n-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\r\n",
    "        L=len(boxes)\r\n",
    "        dp=[[[0]*L for _ in range(L)] for _ in range(L)]\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        def get_points(l,r,k):\r\n",
    "            if l>r:\r\n",
    "                return 0\r\n",
    "            if dp[l][r][k]!=0:\r\n",
    "                return dp[l][r][k]\r\n",
    "            r1=r\r\n",
    "            k1=k\r\n",
    "            while r1>l and boxes[r1-1]==boxes[r1]:\r\n",
    "                r1-=1\r\n",
    "                k1+=1\r\n",
    "            ret=get_points(l,r1-1,0)+(k1+1)**2\r\n",
    "            for i in range(l,r1):\r\n",
    "                if boxes[i]==boxes[r1]:\r\n",
    "                    ret=max(ret,get_points(l,i,k1+1)+get_points(i+1,r1-1,0))\r\n",
    "            dp[l][r][k]=ret\r\n",
    "            return ret\r\n",
    "        return get_points(0,L-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        # 仅仅计算dp[i][j] 表示i->j范围内的最优解是不行的，因为这个分数并不只依赖于子序列，也依赖于后面那些未遍历到的元素。所以这样的dp有后效性\n",
    "        n = len(boxes)\n",
    "        dp = [[[0]*n for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        def calculatePoints(boxes: list, l: int, r: int, k: int) -> int:\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if dp[l][r][k] == 0:\n",
    "                dp[l][r][k] = calculatePoints(boxes, l, r - 1, 0) + (k + 1)**2\n",
    "                for i in range(l, r):\n",
    "                    if boxes[i] == boxes[r]:\n",
    "                        dp[l][r][k] = max(dp[l][r][k], calculatePoints(boxes, l, i, k + 1) + calculatePoints(boxes, i + 1, r - 1, 0))\n",
    "\n",
    "            return dp[l][r][k]\n",
    "        return calculatePoints(boxes, 0, n - 1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        \n",
    "        n = len(boxes)\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        def dfs(i, j, k):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if dp[i][j][k] > 0:\n",
    "                return dp[i][j][k]\n",
    "            res = (k+1) * (k+1) + dfs(i, j-1, 0)\n",
    "            for m in range(i, j):\n",
    "                if boxes[m] == boxes[j]:\n",
    "                    res = max(res, dfs(i, m, k+1) + dfs(m+1, j-1, 0))\n",
    "            dp[i][j][k] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(0, n-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeBoxes(self, boxes: List[int]) -> int:\n",
    "        # Let dp[i][j][k] be max points to remove boxes[i,j] \n",
    "        # if there are k boxes that have the same color as boxes[j] following boxes[j]\n",
    "        # k boxes are subsequences in boxes[j+1:n]\n",
    "        # Base case: if j > i, dp[i][j][k] = 0; dp[i][i][k] = (k + 1)^2\n",
    "        # Consider dp[i][j][k] where j > i.\n",
    "        # Suppose the boxes are now b[i], ... b[j], b[j]-(k)-b[j]\n",
    "        # Then we can delete any subarrays with same color first.\n",
    "\n",
    "        n = len(boxes)\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        def dfs(i, j, k):\n",
    "            if j < i: return 0\n",
    "            if dp[i][j][k] > 0: return dp[i][j][k]\n",
    "            # base case\n",
    "            dp[i][j][k] = dfs(i, j - 1, 0) + (k + 1) ** 2\n",
    "            for p in range(i, j):\n",
    "                if boxes[p] == boxes[j]:\n",
    "                    # boxes[i,...p], {boxes[p+1,...j-1]}, boxes[j], boxes[j]-(k)-boxes[j]\n",
    "                    dp[i][j][k] = max(dp[i][j][k], dfs(i, p, k + 1) + dfs(p + 1, j - 1, 0))\n",
    "            \n",
    "            return dp[i][j][k]\n",
    "        \n",
    "        return dfs(0, n - 1, 0)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
